package leetcode101.search_problem.dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code3
 * @Description 417. Pacific Atlantic Water Flow
 * You are given an m x n integer matrix heights representing the height of each unit cell in a continent.
 * The Pacific ocean touches the continent's left and top edges,
 * and the Atlantic ocean touches the continent's right and bottom edges.
 *
 * Water can only flow in four directions: up, down, left, and right.
 * Water flows from a cell to an adjacent one with an equal or lower height.
 *
 * Return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-30 19:39
 */
public class Code3 {
    public static void main(String[] args) {
        int[][] heights = new int[][] {{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15},{56,57,58,59,60,61,62,63,64,65,66,67,68,69,16},{55,104,105,106,107,108,109,110,111,112,113,114,115,70,17},{54,103,144,145,146,147,148,149,150,151,152,153,116,71,18},{53,102,143,176,177,178,179,180,181,182,183,154,117,72,19},{52,101,142,175,200,201,202,203,204,205,184,155,118,73,20},{51,100,141,174,199,216,217,218,219,206,185,156,119,74,21},{50,99,140,173,198,215,224,225,220,207,186,157,120,75,22},{49,98,139,172,197,214,223,222,221,208,187,158,121,76,23},{48,97,138,171,196,213,212,211,210,209,188,159,122,77,24},{47,96,137,170,195,194,193,192,191,190,189,160,123,78,25},{46,95,136,169,168,167,166,165,164,163,162,161,124,79,26},{45,94,135,134,133,132,131,130,129,128,127,126,125,80,27},{44,93,92,91,90,89,88,87,86,85,84,83,82,81,28},{43,42,41,40,39,38,37,36,35,34,33,32,31,30,29}};
        List<List<Integer>> res = pacificAtlantic(heights);
        System.out.println("synhard");
    }

    public static List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();
        boolean [][] check = new boolean[heights.length][heights[0].length];
        List<Integer> temp;
        for (int i = 0; i < heights.length; i++) {
            for (int j = 0; j < heights[i].length; j++) {
                if (dfsPacific(heights, check, i, j) && dfsAtlantic(heights, check, i, j)) {
                    temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    res.add(temp);
                }
            }
        }
        return res;
    }

    public static boolean dfsPacific(int[][] matrix, boolean[][] check, int i, int j) {
        if (check[i][j]) {
            return false;
        }
        // 如果到达了左边界或上边界
        if (i == 0 || j == 0) {
            return true;
        }
        boolean up = false, down = false, right = false, left = false;
        if (matrix[i - 1][j] <= matrix[i][j]) {
            up = true; // 上面可以走
        }
        if (i < matrix.length - 1 && matrix[i + 1][j] <= matrix[i][j]) {
            down = true; // 下面可以走
        }
        if (matrix[i][j - 1] <= matrix[i][j]) {
            left = true; // 左面可以走
        }
        if (j < matrix[i].length - 1 && matrix[i][j + 1] <= matrix[i][j]) {
            right = true; // 右面可以走
        }
        check[i][j] = true;

        boolean a = up && dfsPacific(matrix, check, i - 1, j);
        boolean b = down && dfsPacific(matrix, check, i + 1, j);
        boolean c = left && dfsPacific(matrix, check, i, j - 1);
        boolean d = right && dfsPacific(matrix, check, i, j + 1);

        check[i][j] = false;

        return a || b || c || d;

    }

    public static boolean dfsAtlantic(int[][] matrix, boolean[][] check, int i, int j) {
        if (check[i][j]) {
            return false;
        }
        // 如果到达了右边界和下边界则返回true
        if (i == matrix.length - 1 || j == matrix[i].length - 1) {
            return true;
        }
        boolean up = false, down = false, right = false, left = false;
        if (i > 0 && matrix[i - 1][j] <= matrix[i][j]) {
            up = true; // 上面可以走
        }
        if (matrix[i + 1][j] <= matrix[i][j]) {
            down = true; // 下面可以走
        }
        if (j > 0 && matrix[i][j - 1] <= matrix[i][j]) {
            left = true; // 左面可以走
        }
        if (matrix[i][j + 1] <= matrix[i][j]) {
            right = true; // 右面可以走
        }

        check[i][j] = true;

        boolean a = up && dfsAtlantic(matrix, check, i - 1, j);
        boolean b = down && dfsAtlantic(matrix, check, i + 1, j);
        boolean c = left && dfsAtlantic(matrix, check, i, j - 1);
        boolean d = right && dfsAtlantic(matrix, check, i, j + 1);

        check[i][j] = false;
        return a || b || c || d;
    }


    private static int[][] dires = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private int m, n;
    private int[][] matrix;

    public List<List<Integer>> pacificAtlantic2(int[][] matrix) {
        List<List<Integer>> res = new ArrayList<>();
        m = matrix.length;
        if (m == 0) {
            return res;
        }
        n = matrix[0].length;
        if (n == 0) {
            return res;
        }
        this.matrix = matrix;
        boolean[][] canReachP = new boolean[m][n];
        boolean[][] canReachA = new boolean[m][n];
        for (int i = 0; i < n; i++) {
            dfs(0, i, canReachP);
            dfs(m - 1, i, canReachA);
        }
        for (int i = 0; i < m; i++) {
            dfs(i, 0, canReachP);
            dfs(i, n - 1, canReachA);
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(canReachA[i][j] && canReachP[i][j]){
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    res.add(temp);
                }
            }
        }
        return res;
    }
    /**
     * 换一种思路，从边界往里面走，只能走到比自己更高或者等高的地方。边界能走到的地方，就是能流入对应海洋的地方。
     */
    private void dfs(int x, int y, boolean[][] canReach) {
        canReach[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int newX = x + dires[i][0];
            int newY = y + dires[i][1];
            if (isIn(newX, newY) && matrix[x][y] <= matrix[newX][newY] && !canReach[newX][newY]) {
                dfs(newX, newY, canReach);
            }
        }
    }

    private boolean isIn(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

}
/*
陆地相当于喷泉，水流可以向四个方向移动，但只能从高处向低处流
找到那些喷泉既可以流动到太平洋又可以流动到大西洋的陆地
思路一是遍历所有的陆地结点去看看这个陆地节点是否可以流通到两个大洋
但是遍历每一个结点的时间复杂度较大，时间复杂度为O(m * n)
我们可以换一种思路，从四周的大洋流向陆地，从低向高流，这样需要遍历的结点为o(m + n)
 */